/*
 * @lc app=leetcode.cn id=572 lang=typescript
 *
 * [572] 另一棵树的子树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

// TODO 遍历和是否为子树并没有什么用处，所以只能暴力破解

// 拆分算法为 1. 判断节点以下的树相等 2. 遍历根树
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
    if (root === null) return false;
    if (isSameTree1(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
const isSameTree1 = (a: TreeNode | null, b: TreeNode | null): boolean => {
    if (a === b) return true;
    if (a === null || b === null) return false;
    if (a.val !== b.val) return false;
    a.left;
    return isSameTree1(a.left, b.left) && isSameTree1(a.right, b.right);
};
// @lc code=end
